from Crypto.Util.number import inverse, long_to_bytes

def crt(vals, mods):
    N = 1
    res = 0
    for i in mods:
        N *= i
    for i in range(len(mods)):
        res += ((N // mods[i]) * inverse(N // mods[i], mods[i]) * vals[i])
    return res

import itertools

def small_roots(f, bounds, m=1, d=None):
	if not d:
		d = f.degree()

	R = f.base_ring()
	N = R.cardinality()
	
	# f /= f.coefficients().pop(0)
	f = f.change_ring(ZZ)

	G = Sequence([], f.parent())
	for i in range(m+1):
		base = N^(m-i) * f^i
		for shifts in itertools.product(range(d), repeat=f.nvariables()):
			g = base * prod(map(power, f.variables(), shifts))
			G.append(g)

	B, monomials = G.coefficient_matrix()
	monomials = vector(monomials)

	factors = [monomial(*bounds) for monomial in monomials]
	for i, factor in enumerate(factors):
		B.rescale_col(i, factor)

	B = B.dense_matrix().LLL()

	B = B.change_ring(QQ)
	for i, factor in enumerate(factors):
		B.rescale_col(i, 1/factor)

	H = Sequence([], f.parent().change_ring(QQ))
	for h in filter(None, B*monomials):
		H.append(h)
		I = H.ideal()
		if I.dimension() == -1:
			H.pop()
		elif I.dimension() == 0:
			roots = []
			for root in I.variety(ring=ZZ):
				root = tuple(R(root[var]) for var in f.variables())
				roots.append(root)
			return roots

	return []

c = 70882700158285084497635919093929071752467677881856729775757529456934863853295282404385474523956264249017514220612279758964352416619258369523102359071406416911207126061452769957316397050977884399144368197815534658557879890133636915280133706802335089891880238596266920465809098066599720551473096231847978797092
N = 138517255214119994790609622354282348739966155100732276677992244162257216490161931530454933533283661099399510534626320390144222006221947703540006227896080001429951326584154966837738564657076410834377917156808075533290671847941245054113754385636450792545690189202517668183504541702525905146859313032149480892861
s = [4758515396635159444505044421424959570593223286583652224392272932793922059831642020040151636828980147966727812313028197408077818356413649460088760754279751172131046144568605834320200630913444827104163940667473391127249936080493, 5292931297426296965606684617062237411526621095943171577847947300868798398382124864921932026236466344620024036624309744113771315270027497269122721426275859673972901123842479633802622069864382702281063051261896029906458751233327, 4530107721319235948266534193028578087934516441915752160369691006744434478691531253130223628034019380708142555802008107270401249900874177123091355255665253951172839005384997426740139070445176977668964571025701980452160019851971, 3262552888094259469183785092536608893114649755835254965599397923543078985315737151513149595755816596970904525728788113099699023171066050654469566099025146182076425689779847798457307717325722164577853425516023208218570874699911]
ff = 4311166391430115243591378775908280256757921744719200708839062619617055843668611960783067111319513519104154288312883661928063335785085675823549644509795474263850412675308539605509849308364294315940948750495977186957267555391674
gg = 3137247880096747914600753210230603868580642037922703148460800329859115318225153400078765700169660560649434930660078749864643505518175382047139411521294391178346585754367780785854476410041695352177502519723771329086874549122836
hh = 2838152196033945595649153876688593973785999408540762211934075878370779266265375907825851137091863689216137000077646220879767570068828797399347714564631166448590659584416821630554314860742959485029648836470850398255810131208461
ll = 1895029368946328810987014190090526467314434255188097876852526222523948408161996353973268762662954555219142022104749268835730455678609266570065307750283306621171283864426059619749600671049354876301554530144856673559961352963291

n = s[0] * s[1] * s[2] * s[3]

F.<x, y> = ZZ[]

vals = [
	(17 * x**2 + 27 * y**2) - ff,
	(31 * x + 71 * y + 107 * x * y) - gg,
	(x**2 + y**2 + x + y + x * y) - hh,
	(11 * x**2 + 51 * x * y + 13 * y) - ll
]

f = (crt(vals, s)).change_ring(Zmod(n))

# t = gcd(int(f.coefficients().pop(0)), N)

# f = (f.change_ring(ZZ) / t).change_ring(Zmod(N/t))

r = small_roots(f, [2^513, 2^513], m=5, d=5)[0]

for p in r:
	p = int(p)
	if (N % p != 0): continue
	q = N//p
	phi = (p-1) * (q-1)
	e = 0x10001
	d = pow(e, -1, phi)
	m = pow(c, d, N)
	print(long_to_bytes(int(m)))




